package homework10package;
/**
 * pageRank class
 * 
 * this class provides methods for implementing the page rank algorithm
 * 
 * @author      Lisa Park and Orion Taylor
 * @course Software Engineering
 * @date 2-2-13
 */

import java.util.HashMap;
import java.util.HashSet;

public class pageRank {
	
	/**UpdateRank()
	 * 
	 * this function updates the page rank of a given web index
	 *  
	 * @param a representation of the web index that we want to
	 * update the page rank of
	 * 
	 * @param epsilon: a factor representing how accurate we want
	 * our page rank to be (for the stopping condition)
	 */
	public void UpdateRank(Index myIndex,double epsilon){
		
		//do one increment for safesies
		myIndex.setUrlRank(this.IterateRank(myIndex.getForward_edge_map(),
				myIndex.getUrlRank()));
		
		//numpages is the number of url's that we are ranking
		double numpages=myIndex.getForward_edge_map().size();
		
		double difference=epsilon/numpages+1;
		
		//while the pageRank is still changing significantly...
		do{
			
			//newRank is the next iteration of pageRank
			HashMap<Integer,Double> newRank=
					this.IterateRank(myIndex.getForward_edge_map(),
									 myIndex.getUrlRank());
			
			//calculate the absolute difference between old and new page ranks
			difference=this.rankDiff(newRank, myIndex.getUrlRank());
			
			//set the old page rank to the new page rank
			myIndex.setUrlRank(newRank);
			
		}while(difference>epsilon/numpages);
		
	}
	
	/**rankDiff()
	 * 
	 * this computes the absolute difference between two page ranks
	 *  
	 * @param urlRank1: the first page rank
	 * @param urlRank2: the second page rank
	 * 
	 * @return double: the absolute difference of the two page ranks
	 */
	private double rankDiff(HashMap<Integer,Double> urlRank1,
			HashMap<Integer,Double> urlRank2){
		
		//accumulator will accumulate the absolute differences between the ranks
		double accumulator=0;
		
		//iterate through the entries of the page ranks
		for(Integer r:urlRank1.keySet()){
			
			//increment the accumulator by the absolute difference of
			//given set of entries in the page ranks
			accumulator= accumulator+
					Math.abs(urlRank1.get(r).doubleValue()-urlRank2.get(r).doubleValue());
		}
		
		return accumulator;
	}
	
	/**IterateRank()
	 * 
	 * this function iterates a step forward in the page rank algorithm
	 * 
	 * @param forward_term_map: maps urls to the terms on their page
	 * and their corresponding pair frequencies
	 * 
	 * @param urlRank: maps url's to their respective page ranks
	 * @return HashMap<Integer,Double> : the new page ranks
	 */
	private HashMap<Integer,Double> IterateRank(
			HashMap<Integer,HashSet<Integer>> forward_edge_map,
			HashMap<Integer,Double> urlRank){
	
		//d is the damping factor
		double d =.85;
		
		//N is the number of webpages
		int N = forward_edge_map.size();
		
		//base_value is the base value for the new page rank number
		double base_value= (1-d)/((double)N);
		
		//newRank will be our new pageRank
		HashMap<Integer,Double> newRank=new HashMap<Integer,Double> ();
		
		//iterate through all the url's
		for(Integer urlIndex:forward_edge_map.keySet()){
			//initialize all values in the new page rank to base_value
			newRank.put(urlIndex, base_value);
		}
		
		//iterate through all the url's
		for(Integer urlIndex:forward_edge_map.keySet()){
			
			//forward_links is the sets of urls linked to by urlIndex
			HashSet<Integer> forward_links= forward_edge_map.get(urlIndex);
			
			//number of outward links held by the url at urlindex that
			//link back to pages that we actually have information of
			double relevant_links=0;
			
			//iterate through each link linked to by url at urlindex
			for(Integer link: forward_links){
				
				//if the linked page is actually one that we have
				if(newRank.containsKey(link)){
					
					//thenk increment relevant_links (to account for this fact)
					relevant_links++;
				}
			}
			
			//iterate through each link linked to by url at urlindex
			for(Integer link: forward_links){
				if(newRank.containsKey(link) && urlRank.containsKey(urlIndex)){
					
					//for each link, increment the new pageRank accordingly
					newRank.put(link, newRank.get(link).doubleValue()
							+ urlRank.get(urlIndex).doubleValue()*d/relevant_links);
				}
			}
		}
		
		//return new version of page rank
		return newRank;	
	}
}
